|
Algebraic-group factorisation algorithms are algorithms for factoring an integer ''N'' by working in an algebraic group defined modulo ''N'' whose group structure is the direct sum of the 'reduced groups' obtained by performing the equations defining the group arithmetic modulo the unknown prime factors ''p''1, ''p''2, ... By the Chinese remainder theorem, arithmetic modulo ''N'' corresponds to arithmetic in all the reduced groups simultaneously. The aim is to find an element which is not the identity of the group modulo ''N'', but is the identity modulo one of the factors, so a method for recognising such ''one-sided identities'' is required. In general, one finds them by performing operations that move elements around and leave the identities in the reduced groups unchanged. Once the algorithm finds a one-sided identity all future terms will also be one-sided identities, so checking periodically suffices. Computation proceeds by picking an arbitrary element ''x'' of the group modulo ''N'' and computing a large and smooth multiple ''Ax'' of it; if the order of at least one but not all of the reduced groups is a divisor of A, this yields a factorisation. It need not be a prime factorisation, as the element might be an identity in more than one of the reduced groups. Generally, A is taken as a product of the primes below some limit K, and ''Ax'' is computed by successive multiplication of ''x'' by these primes; after each multiplication, or every few multiplications, the check is made for a one-sided identity. == The two-step procedure == It is often possible to multiply a group element by several small integers more quickly than by their product, generally by difference-based methods; one calculates differences between consecutive primes and adds consecutively by the . This means that a two-step procedure becomes sensible, first computing ''Ax'' by multiplying ''x'' by all the primes below a limit B1, and then examining ''p Ax'' for all the primes between B1 and a larger limit B2. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Algebraic-group factorisation algorithm」の詳細全文を読む スポンサード リンク
|